package com.readen.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * {@link https://oj.leetcode.com/problems/subsets/ }
 *  
Given a set of distinct integers, S, return all possible subsets.

Note:

    Elements in a subset must be in non-descending order.
    The solution set must not contain duplicate subsets.

 * @author Administrator
 *
 */
public class Subsets {

	 private int[] intSet;
	 private int len;
	 private List<List<Integer>> result;
	 
	 
	 public List<List<Integer>> getSubsets(int[] S) {
	  intSet=S;   
	  result=new ArrayList<List<Integer>>();
	  Arrays.sort(intSet);
	  len=intSet.length;
	  result.add(new ArrayList<Integer>());
	  for(int sLen=1;sLen<=len;sLen++){  //**选出不同的组合
		  int[] sub=new int[sLen];
		  calIndexAt(0,sub);
	  }
	  return result; 
	 }
	
	private void calIndexAt(int pos,int[] indexs){
		if(pos==0){
			for(int i=0;i<len-indexs.length+1;i++){
				indexs[0]=i;
				if(indexs.length==1){
					ArrayList<Integer> oneSet=new ArrayList<Integer>();	
					oneSet.add(intSet[indexs[0]]);
					result.add(oneSet);
				}else{
					calIndexAt(1, indexs);
				}
			}
			return;
		}
		if(pos==indexs.length-1){
			for(int j=indexs[pos-1]+1;j<len;j++){
				indexs[pos]=j;
				ArrayList<Integer> oneSet=new ArrayList<Integer>();
				for(int k=0;k<indexs.length;k++){
					oneSet.add(intSet[indexs[k]]);
				}
				result.add(oneSet);
			}
		}else{
			int remain=Math.max(indexs.length-1-pos, 0);//剩余元素的个数
			for(int j=indexs[pos-1]+1;j<len;j++){
				if(j+remain<len){
					indexs[pos]=j;
					calIndexAt(pos+1,indexs);
				}
			}
		}
	}
	 
	

}
